package leetcode.weekly.week305;

//Solution4Test
public class Solution4 {

	public int longestIdealString(String s, int k) {
		char[] cs = s.toCharArray();
		int[] ends = new int[26];
		int ans = 0;
		for (int i = 0; i < cs.length; i++) {
			int c = cs[i] - 'a';
			for (int j = Math.max(0, c - k); j <= Math.min(25, c + k); j++) {// Math.abs(j - c) <= k &&
				if (ends[c] < ends[j]) {
					ends[c] = ends[j];
				}
			}
			ans = Math.max(++ends[c], ans);
		}
		return ans;
	}

	public int longestIdealString1(String s, int k) {
		char[] cs = s.toCharArray();
		int[] ends = new int[26];
		int ans = 0;
		for (int i = 0; i < cs.length; i++) {
			int c = cs[i] - 'a';
			ends[c] = ends[c] + 1;
			ans = Math.max(ans, ends[c]);
			for (int j = 0; j < 26; j++) {
				if (j != c && Math.abs(j - c) <= k && ends[c] < ends[j] + 1) {
					ends[c] = ends[j] + 1;
					ans = Math.max(ends[c], ans);
				}
			}
		}
		return ans;
	}
}
